{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Product of Two Run-Length Encoded Arrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findRLEArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #两个行程编码数组的积"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><b>行程编码（</b><strong>Run-length encoding）</strong>是一种压缩算法，能让一个含有许多段<strong>连续重复</strong>数字的整数类型数组 <code>nums</code> 以一个（通常更小的）二维数组 <code>encoded</code> 表示。每个 <code>encoded[i] = [val<sub>i</sub>, freq<sub>i</sub>]</code> 表示 <code>nums</code> 中第 <code>i</code> 段重复数字，其中 <code>val<sub>i</sub></code> 是该段重复数字，重复了 <code>freq<sub>i</sub></code> 次。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如， <code>nums = [1,1,1,2,2,2,2,2]</code> 可表示称行程编码数组 <code>encoded = [[1,3],[2,5]]</code> 。对此数组的另一种读法是“三个 <code>1</code> ，后面有五个 <code>2</code> ”。</li>\n",
    "</ul>\n",
    "\n",
    "<p>两个行程编码数组 <code>encoded1</code> 和 <code>encoded2</code> 的积可以按下列步骤计算：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>将 <code>encoded1</code> 和 <code>encoded2</code> 分别<strong>扩展</strong>成完整数组 <code>nums1</code> 和 <code>nums2</code> 。</li>\n",
    "\t<li>创建一个新的数组 <code>prodNums</code> ，长度为 <code>nums1.length</code> 并设 <code>prodNums[i] = nums1[i] * nums2[i]</code> 。</li>\n",
    "\t<li>将 <code>prodNums</code> <strong>压缩</strong>成一个行程编码数组并返回之。</li>\n",
    "</ol>\n",
    "\n",
    "<p>给定两个<strong>行程编码</strong>数组 <code>encoded1</code> 和 <code>encoded2</code> ，分别表示完整数组 <code>nums1</code> 和 <code>nums2</code> 。<code>nums1</code> 和 <code>nums2</code> 的<strong>长度相同</strong>。 每一个 <code>encoded1[i] = [val<sub>i</sub>, freq<sub>i</sub>]</code> 表示 <code>nums1</code> 中的第 <code>i</code> 段，每一个 <code>encoded2[j] = [val<sub>j</sub>, freq<sub>j</sub>]</code> 表示 <code>nums2</code> 中的第 <code>j</code> 段。</p>\n",
    "\n",
    "<p>返回<i> </i><code>encoded1</code> 和 <code>encoded2</code> 的<strong>乘积</strong>。</p>\n",
    "\n",
    "<p><b>注：</b>行程编码数组需压缩成可能的<strong>最小</strong>长度。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><b>示例 1:</b></p>\n",
    "\n",
    "<pre><strong>输入:</strong> encoded1 = [[1,3],[2,3]], encoded2 = [[6,3],[3,3]]\n",
    "<strong>输出:</strong> [[6,6]]\n",
    "<strong>解释n:</strong> encoded1 扩展为 [1,1,1,2,2,2] ，encoded2 扩展为 [6,6,6,3,3,3]。\n",
    "prodNums = [6,6,6,6,6,6]，压缩成行程编码数组 [[6,6]]。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> encoded1 = [[1,3],[2,1],[3,2]], encoded2 = [[2,3],[3,3]]\n",
    "<strong>输出:</strong> [[2,3],[6,1],[9,2]]\n",
    "<strong>解释:</strong> encoded1 扩展为 [1,1,1,2,3,3] ，encoded2 扩展为 [2,2,2,3,3,3]。\n",
    "prodNums = [2,2,2,6,9,9]，压缩成行程编码数组 [[2,3],[6,1],[9,2]]。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><b>提示：</b></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= encoded1.length, encoded2.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>encoded1[i].length == 2</code></li>\n",
    "\t<li><code>encoded2[j].length == 2</code></li>\n",
    "\t<li>对于每一个 <code>encoded1[i]</code>， <code>1 &lt;= val<sub>i</sub>, freq<sub>i</sub> &lt;= 10<sup>4</sup></code>  </li>\n",
    "\t<li>对于每一个 <code>encoded2[j]</code>， <code>1 &lt;= val<sub>j</sub>, freq<sub>j</sub> &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>encoded1</code> 和 <code>encoded2</code> 表示的完整数组长度相同。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [product-of-two-run-length-encoded-arrays](https://leetcode.cn/problems/product-of-two-run-length-encoded-arrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [product-of-two-run-length-encoded-arrays](https://leetcode.cn/problems/product-of-two-run-length-encoded-arrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,3],[2,3]]\\n[[6,3],[3,3]]', '[[1,3],[2,1],[3,2]]\\n[[2,3],[3,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRLEArray(self, encoded1: List[List[int]], encoded2: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(encoded1)\n",
    "        n = len(encoded2)\n",
    "\n",
    "        result =[[-1, 0]]\n",
    "\n",
    "        i = 0 \n",
    "        j = 0\n",
    "\n",
    "        while i < m:\n",
    "            count = min(encoded1[i][1], encoded2[j][1])\n",
    "            value = encoded1[i][0] * encoded2[j][0]\n",
    "\n",
    "            if value == result[-1][0]:\n",
    "                result[-1][1] += count\n",
    "            else:\n",
    "                result.append([value, count])\n",
    "            \n",
    "            encoded1[i][1] -= count\n",
    "            if encoded1[i][1] <= 0:\n",
    "                i += 1\n",
    "            \n",
    "            encoded2[j][1] -= count\n",
    "            if encoded2[j][1] <= 0:\n",
    "                j += 1\n",
    "        \n",
    "        return result[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRLEArray(self, encoded1: List[List[int]], encoded2: List[List[int]]) -> List[List[int]]:\n",
    "        idx1 = 0\n",
    "        idx2 = 0\n",
    "        ans = list()\n",
    "        tmp1 = 0\n",
    "        tmp2 = 0\n",
    "        last = 0\n",
    "        lastlen = 0\n",
    "        while idx1 < len(encoded1) and idx2 < len(encoded2):\n",
    "            if encoded1[idx1][1] - tmp1 < encoded2[idx2][1] - tmp2:\n",
    "                if encoded2[idx2][0] * encoded1[idx1][0] == last:\n",
    "                    lastlen += encoded1[idx1][1] - tmp1\n",
    "                else:\n",
    "                    ans.append([last, lastlen])\n",
    "                    last = encoded2[idx2][0] * encoded1[idx1][0]\n",
    "                    lastlen = encoded1[idx1][1] - tmp1\n",
    "                tmp2 += encoded1[idx1][1] - tmp1\n",
    "                tmp1 = 0\n",
    "                idx1 += 1\n",
    "            elif encoded1[idx1][1] - tmp1 > encoded2[idx2][1] - tmp2:\n",
    "                if encoded2[idx2][0] * encoded1[idx1][0] == last:\n",
    "                    lastlen += encoded2[idx2][1] - tmp2\n",
    "                else:\n",
    "                    ans.append([last, lastlen])\n",
    "                    last = encoded2[idx2][0] * encoded1[idx1][0]\n",
    "                    lastlen = encoded2[idx2][1] - tmp2\n",
    "                tmp1 += encoded2[idx2][1]- tmp2\n",
    "                tmp2 = 0\n",
    "                idx2 += 1\n",
    "            else:\n",
    "                if encoded2[idx2][0] * encoded1[idx1][0] == last:\n",
    "                    lastlen += encoded2[idx2][1] - tmp2\n",
    "                else:\n",
    "                    ans.append([last, lastlen])\n",
    "                    last = encoded2[idx2][0] * encoded1[idx1][0]\n",
    "                    lastlen = encoded2[idx2][1] - tmp2\n",
    "                tmp1 = 0\n",
    "                tmp2 = 0\n",
    "                idx2 += 1\n",
    "                idx1 += 1\n",
    "        ans.append([last, lastlen])\n",
    "        return ans[1::]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def findRLEArray(self, encoded1: List[List[int]], encoded2: List[List[int]]) -> List[List[int]]:\n",
    "        i, j = 0, 0\n",
    "        res = []\n",
    "        \n",
    "        prev_val, prev_freq = None, 0\n",
    "        \n",
    "        while i < len(encoded1) and j < len(encoded2):\n",
    "            val = encoded1[i][0] * encoded2[j][0]\n",
    "            freq = min(encoded1[i][1], encoded2[j][1])\n",
    "            \n",
    "            if prev_val is None or prev_val == val:\n",
    "                prev_val = val\n",
    "                prev_freq += freq\n",
    "            else:\n",
    "                res.append([prev_val, prev_freq])\n",
    "                prev_val = val\n",
    "                prev_freq = freq\n",
    "                \n",
    "            # Update frequencies and move pointers if needed\n",
    "            encoded1[i][1] -= freq\n",
    "            encoded2[j][1] -= freq\n",
    "            if encoded1[i][1] == 0:\n",
    "                i += 1\n",
    "            if encoded2[j][1] == 0:\n",
    "                j += 1\n",
    "        \n",
    "        # Handle any remaining values\n",
    "        if prev_val is not None:\n",
    "            res.append([prev_val, prev_freq])\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRLEArray(self, encoded1: List[List[int]], encoded2: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(encoded1), len(encoded2)\n",
    "        ans = [[-1, 0]]\n",
    "        i = j = 0\n",
    "        while i < m:\n",
    "            cnt = min(encoded1[i][1], encoded2[j][1])\n",
    "            num = encoded1[i][0] * encoded2[j][0]\n",
    "            if num == ans[-1][0]:\n",
    "                ans[-1][1] += cnt\n",
    "            else:\n",
    "                ans.append([num, cnt])\n",
    "\n",
    "            encoded1[i][1] -= cnt\n",
    "            if not encoded1[i][1]:\n",
    "                i += 1\n",
    "            encoded2[j][1] -= cnt\n",
    "            if not encoded2[j][1]:\n",
    "                j += 1\n",
    "        return ans[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRLEArray(self, encoded1: List[List[int]], encoded2: List[List[int]]) -> List[List[int]]:\n",
    "        l1, l2 = len(encoded1), len(encoded2)\n",
    "        p, q = 0, 0\n",
    "        cnt = 0\n",
    "        ans = [[None, 0]]\n",
    "\n",
    "        for i in range(1, l1):\n",
    "            encoded1[i][1] += encoded1[i-1][1]\n",
    "        for i in range(1, l2):\n",
    "            encoded2[i][1] += encoded2[i-1][1]\n",
    "        \n",
    "        while (p<l1) and (q<l2):\n",
    "            n1, c1 = encoded1[p]\n",
    "            n2, c2 = encoded2[q]\n",
    "            \n",
    "            c = min(c1, c2)\n",
    "            prod = n1*n2\n",
    "            rep = c - cnt\n",
    "            if prod == ans[-1][0]:\n",
    "                ans[-1][1] = ans[-1][1]+rep\n",
    "            else:\n",
    "                ans.append([prod, rep])\n",
    "\n",
    "            cnt = c\n",
    "            if c1 == cnt:\n",
    "                p +=1\n",
    "            if c2 == cnt:\n",
    "                q+=1\n",
    "        \n",
    "        return ans[1:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def findRLEArray(self, encoded1: List[List[int]], encoded2: List[List[int]]) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param encoded1:\n",
    "        :param encoded2:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        dq1 = deque()\n",
    "        dq2 = deque()\n",
    "        for i in encoded1:\n",
    "            dq1.append(i)\n",
    "        for i in encoded2:\n",
    "            dq2.append(i)\n",
    "        tmp1 = []\n",
    "        while dq1 and dq2:\n",
    "            v1, cnt1 = dq1[0]\n",
    "            v2, cnt2 = dq2[0]\n",
    "            if cnt1 <= cnt2:\n",
    "                dq1.popleft()\n",
    "                tmp1.append((v1*v2, cnt1))\n",
    "                rest = cnt2 - cnt1\n",
    "                dq2.popleft()\n",
    "                if rest > 0:\n",
    "                    dq2.insert(0, (v2, rest))\n",
    "            else:\n",
    "                dq2.popleft()\n",
    "                tmp1.append((v1*v2, cnt2))\n",
    "                rest = cnt1 - cnt2\n",
    "                dq1.popleft()\n",
    "                if rest > 0:\n",
    "                    dq1.insert(0, (v1, rest))\n",
    "        ret2 = []\n",
    "        prev = None\n",
    "        cnt = 0\n",
    "        for k,v in enumerate(tmp1):\n",
    "            if prev is None:\n",
    "                prev = v[0]\n",
    "                cnt = v[1]\n",
    "            else:\n",
    "                if prev == v[0]:\n",
    "                    cnt += v[1]\n",
    "                else:\n",
    "                    ret2.append((prev, cnt))\n",
    "                    prev = v[0]\n",
    "                    cnt = v[1]\n",
    "        if cnt > 0:\n",
    "            ret2.append((prev, cnt))\n",
    "        return ret2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def findRLEArray(self, encoded1: List[List[int]], encoded2: List[List[int]]) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param encoded1:\n",
    "        :param encoded2:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        dq1 = deque()\n",
    "        dq2 = deque()\n",
    "        for i in encoded1:\n",
    "            dq1.append(i)\n",
    "        for i in encoded2:\n",
    "            dq2.append(i)\n",
    "        tmp1 = []\n",
    "        while dq1 and dq2:\n",
    "            v1, cnt1 = dq1[0]\n",
    "            v2, cnt2 = dq2[0]\n",
    "            if cnt1 <= cnt2:\n",
    "                dq1.popleft()\n",
    "                tmp1.append((v1*v2, cnt1))\n",
    "                rest = cnt2 - cnt1\n",
    "                dq2.popleft()\n",
    "                if rest > 0:\n",
    "                    dq2.insert(0, (v2, rest))\n",
    "            else:\n",
    "                dq2.popleft()\n",
    "                tmp1.append((v1*v2, cnt2))\n",
    "                rest = cnt1 - cnt2\n",
    "                dq1.popleft()\n",
    "                if rest > 0:\n",
    "                    dq1.insert(0, (v1, rest))\n",
    "        ret2 = []\n",
    "        prev = None\n",
    "        cnt = 0\n",
    "        for k,v in enumerate(tmp1):\n",
    "            if prev is None:\n",
    "                prev = v[0]\n",
    "                cnt = v[1]\n",
    "            else:\n",
    "                if prev == v[0]:\n",
    "                    cnt += v[1]\n",
    "                else:\n",
    "                    ret2.append((prev, cnt))\n",
    "                    prev = v[0]\n",
    "                    cnt = v[1]\n",
    "\n",
    "        ret2.append((prev, cnt))\n",
    "        return ret2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def findRLEArray(self, encoded1: List[List[int]], encoded2: List[List[int]]) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param encoded1:\n",
    "        :param encoded2:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        dq1 = deque()\n",
    "        dq2 = deque()\n",
    "        for i in encoded1:\n",
    "            dq1.append(i)\n",
    "        for i in encoded2:\n",
    "            dq2.append(i)\n",
    "        tmp1 = []\n",
    "        while dq1 and dq2:\n",
    "            v1, cnt1 = dq1[0]\n",
    "            v2, cnt2 = dq2[0]\n",
    "            if cnt1 <= cnt2:\n",
    "                dq1.popleft()\n",
    "                tmp1.append((v1*v2, cnt1))\n",
    "                rest = cnt2 - cnt1\n",
    "                dq2.popleft()\n",
    "                if rest > 0:\n",
    "                    dq2.insert(0, (v2, rest))\n",
    "            else:\n",
    "                dq2.popleft()\n",
    "                tmp1.append((v1*v2, cnt2))\n",
    "                rest = cnt1 - cnt2\n",
    "                dq1.popleft()\n",
    "                if rest > 0:\n",
    "                    dq1.insert(0, (v1, rest))\n",
    "        ret2 = []\n",
    "        prev = None\n",
    "        cnt = 0\n",
    "        for k,v in enumerate(tmp1):\n",
    "            if prev is None:\n",
    "                prev = v[0]\n",
    "                cnt = v[1]\n",
    "            else:\n",
    "                if prev == v[0]:\n",
    "                    cnt += v[1]\n",
    "                else:\n",
    "                    ret2.append((prev, cnt))\n",
    "                    prev = v[0]\n",
    "                    cnt = v[1]\n",
    "        if cnt > 0:\n",
    "            ret2.append((prev, cnt))\n",
    "        return ret2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def findRLEArray(self, encoded1: List[List[int]], encoded2: List[List[int]]) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param encoded1:\n",
    "        :param encoded2:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        dq1 = deque()\n",
    "        dq2 = deque()\n",
    "        for i in encoded1:\n",
    "            dq1.append(i)\n",
    "        for i in encoded2:\n",
    "            dq2.append(i)\n",
    "        tmp1 = []\n",
    "        while dq1 and dq2:\n",
    "            v1, cnt1 = dq1[0]\n",
    "            v2, cnt2 = dq2[0]\n",
    "            if cnt1 <= cnt2:\n",
    "                dq1.popleft()\n",
    "                tmp1.append((v1*v2, cnt1))\n",
    "                rest = cnt2 - cnt1\n",
    "                dq2.popleft()\n",
    "                if rest > 0:\n",
    "                    dq2.insert(0, (v2, rest))\n",
    "            else:\n",
    "                dq2.popleft()\n",
    "                tmp1.append((v1*v2, cnt2))\n",
    "                rest = cnt1 - cnt2\n",
    "                dq1.popleft()\n",
    "                if rest > 0:\n",
    "                    dq1.insert(0, (v1, rest))\n",
    "        ret2 = []\n",
    "        prev = None\n",
    "        cnt = 0\n",
    "        for k,v in enumerate(tmp1):\n",
    "            if prev is None:\n",
    "                prev = v[0]\n",
    "                cnt = v[1]\n",
    "            else:\n",
    "                if prev == v[0]:\n",
    "                    cnt += v[1]\n",
    "                else:\n",
    "                    ret2.append((prev, cnt))\n",
    "                    prev = v[0]\n",
    "                    cnt = v[1]\n",
    "        if cnt > 0:\n",
    "            ret2.append((prev, cnt))\n",
    "        return ret2\n",
    "\n",
    "a = Solution()\n",
    "print(a.findRLEArray(encoded1 = [[1,3],[2,1],[3,2]], encoded2 = [[2,3],[3,3]] ))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def findRLEArray(self, encoded1: List[List[int]], encoded2: List[List[int]]) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param encoded1:\n",
    "        :param encoded2:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        dq1 = deque()\n",
    "        dq2 = deque()\n",
    "        for i in encoded1:\n",
    "            dq1.append(i)\n",
    "        for i in encoded2:\n",
    "            dq2.append(i)\n",
    "        tmp1 = []\n",
    "        while dq1 and dq2:\n",
    "            v1, cnt1 = dq1[0]\n",
    "            v2, cnt2 = dq2[0]\n",
    "            if cnt1 <= cnt2:\n",
    "                dq1.popleft()\n",
    "                tmp1.append((v1*v2, cnt1))\n",
    "                rest = cnt2 - cnt1\n",
    "                dq2.popleft()\n",
    "                if rest > 0:\n",
    "                    dq2.insert(0, (v2, rest))\n",
    "            else:\n",
    "                dq2.popleft()\n",
    "                tmp1.append((v1*v2, cnt2))\n",
    "                rest = cnt1 - cnt2\n",
    "                dq1.popleft()\n",
    "                if rest > 0:\n",
    "                    dq1.insert(0, (v1, rest))\n",
    "        ret2 = []\n",
    "        prev = None\n",
    "        cnt = 0\n",
    "        for k,v in enumerate(tmp1):\n",
    "            if prev is None:\n",
    "                prev = v[0]\n",
    "                cnt = v[1]\n",
    "            else:\n",
    "                if prev == v[0]:\n",
    "                    cnt += v[1]\n",
    "                else:\n",
    "                    ret2.append((prev, cnt))\n",
    "                    prev = v[0]\n",
    "                    cnt = v[1]\n",
    "        if cnt > 0:\n",
    "            ret2.append((prev, cnt))\n",
    "        return ret2\n",
    "\n",
    "a = Solution()\n",
    "print(a.findRLEArray(encoded1 = [[1,3],[2,1],[3,2]], encoded2 = [[2,3],[3,3]] ))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
